/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.medium._08_07;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 无重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合，字符串每个字符均不相同。
 *
 * 示例1:
 *
 *  输入：S = "qwe"
 *  输出：["qwe", "qew", "wqe", "weq", "ewq", "eqw"]
 * 示例2:
 *
 *  输入：S = "ab"
 *  输出：["ab", "ba"]
 * 提示:
 *
 * 字符都是英文字母。
 * 字符串长度在[1, 9]之间。
 *
 *
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.medium._08_07
 * @ClassName: Permutation
 * @Author: linyaonan
 * @Date: 2020/3/24 11:41
 */
public class Permutation {

    public String[] permutation(String S) {
        char[] chars = S.toCharArray();
        StringBuilder sb = new StringBuilder();
        // 频繁的指定位置删除，插入
        LinkedList<Character> list = new LinkedList<>();
        for (char c : chars) {
            list.add(c);
        }
        // 只添加
        ArrayList<String> result = new ArrayList<>();
        bt(sb, list, result);
        String[] s = new String[result.size()];
        for (int i = 0; i < result.size(); i++) {
            s[i] = result.get(i);
        }
        return s;
    }

    /**
     * 回溯算法
     * @param sb
     * @param list
     * @param result
     */
    private void bt(StringBuilder sb, List<Character> list, List<String> result) {
        if (list.size() == 0) {
            result.add(sb.toString());
        } else {
            for (int i = 0; i < list.size(); i++) {
                sb.append(list.get(i));
                Character remove = list.remove(i);
                bt(sb,list, result);
                // 回溯
                sb.delete(sb.length() - 1, sb.length());
                list.add(i, remove);
            }
        }
    }

}
